This invention relates to a method for finding a shortest path and a computer-readable record media storing instructions for performing the method; and more particularly, to a method for finding a shortest path in a traffic network using a Dijkstra algorithm and a Floyd-warshall algorithm and a computer-readable record media storing instructions for performing the method.
A Dijkstra algorithm and a Floyd-warshall algorithm are ones, which are frequently used for finding a shortest path.
The conventional Dijkstra algorithm makes it possible to find a shortest travel time value from a starting node to all other nodes in a network with nonnegative arc values. According to this algorithm, all nodes are classified into two groups of node. One is a permanent node that represents a shortest travel time value from a starting node to a relevant node. The other one is a temporary node that represents an upper bound of a real shortest travel time value from the starting node to the relevant node. Also, a label of a node refers to a shortest travel time value from the starting node along a path whose internal nodes are all permanently labeled. Initially, the starting node is labeled with the permanent node whose travel time value is zero.
According to the Dijkstra algorithm, a node having a minimum temporary label is selected to thereby become the permanent node. The Dijkstra algorithm terminates when all nodes including from the relevant node to neighboring nodes become the permanent node.
The Floyd-warshall algorithm makes it possible to find a shortest path between all pairs of nodes in a network.
According to the Floyd-warshall algorithm, a matrix of xcfx80ij is computed. The xcfx80ij denotes a travel time value for each of all pairs of nodes, i and j. A xcfx80ij(m) denotes a matrix of a shortest travel time value from the node i and to the node j using 1, 2, . . . , mxe2x88x921 as the internal node. A xcfx80ij(k) denotes a matrix of a travel time value for each of all pairs of nodes i and j within a starting node and an arrival node. A xcfx80ij(k+1) is computed based on the xcfx80ij(k). Here, a Triple operation needs to be performed in order to compute the xcfx80ij(k+1).
FIG. 7 shows one embodiment of a Triple operation according to a Floyd-warshall algorithm.
Here, it is supposed that a xcfx80ij(m) denotes a matrix for a shortest travel time value from the node i and to the node j using 1, 2, . . . , mxe2x88x921 as an internal node. A xcfx80ij(k+1) is generated by calculating a given xcfx80ij(k) on a following Triple operation.
That is to say, as for a shortest travel time using nodes 1, 2, . . . , k as an internal node, if xcfx80ij(k) less than xcfx80ik(k)+xcfx80kj(k), xcfx80ij(k)=xcfx80ij(k+1) without passing a node k, however if xcfx80ij(k) greater than xcfx80ik(k)+xcfx80kj(k), xcfx80ij(k)=xcfx80ik(k)+xcfx80kj(k) with passing the node k.
When representing the above by a mathematical equation, the equation is as follows:
xcfx80ij(k+1)=min {xcfx80ij(k), xcfx80ik(k)+xcfx80kj(k)}
In other words, a less one of xcfx80ij(k) and xcfx80ik(k)+xcfx80kj(k) is assigned to xcfx80ij(k+1).
As described above, the conventional Dijkstra algorithm and Floyd-warshall algorithm are used to find a shortest path, however there is a problem that the same node should not be passed twice. Also, there is another problem that the above two algorithm cannot be applied to a real traffic network, in which a Left-turn restriction, a U-turn and a P-turn are included.
It is an object of the present invention to provide a method for finding a shortest path from a starting place to a destination place in a traffic network to thereby reach the destination place in shorter time.
In accordance with an aspect of the present invention, there is provided a method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm, the method including the steps of: assigning a virtual arc connection value from a starting node to a destination node based on traffic information in order to do the turn restriction, the U-turn and the P-turn, wherein the starting node indicates the starting place and the destination node indicates the destination place; selecting a smallest travel time value out of total travel time value for a temporary label node from the starting node to all nodes except for the starting node and assigning the smallest travel time value to a permanent label node; and determining the shortest path by tracing a permanent node stating from the destination node.